/*
 * @lc app=leetcode.cn id=796 lang=cpp
 *
 * [796] 旋转字符串
 */

// @lc code=start
class Solution
{
public:
    void getNext(string &patten, vector<int> &next)
    {
        next[0] = -1;
        for (int i = 1, j = -1; i < patten.size(); i++)
        {
            while (j != -1 && patten[i] != patten[j + 1])
            {
                j = next[j];
            }
            if (patten[i] == patten[j + 1])
            {
                j++;
            }
            next[i] = j;
        }
    }
    int kmp(string &s, string &goal, vector<int> &next)
    {
        for (int i = 0, j = -1; i < s.size(); i++)
        {
            while (j != -1 && s[i] != goal[j + 1])
            {
                j = next[j];
            }
            if (s[i] == goal[j + 1])
            {
                j++;
            }
            if (j == goal.size() - 1)
            {
                return i - j;
            }
        }
        return -1;
    }
    bool rotateString(string s, string goal)
    {
        int m = s.size(), n = goal.size();
        if (m != n)
        {
            return false;
        }

        string s1 = s + s;
        vector<int> next(n, 0);
        getNext(goal, next);

        return kmp(s1, goal, next) != -1;
    }
};
// @lc code=end
